Sau khi ta đã định nghĩa được một hàm trả về thích hợp cần được cực đại hóa, ta cần chỉ rõ thuật toán sẽ được sử dụng để tìm chiến lược thu được kết quả trả về cao nhất. Có hai cách tiếp cận chính, cách tiếp cận hàm giá trị và cách tiếp cận trực tiếp.

Cách tiếp cận trực tiếp dẫn đến hai bước sau đây:

1. Với mỗi chiến lược có thể, lấy mẫu các kết quả trong khi thực hiện chiến lược đó.
2. Chọn chiến lược có kết quả trả về kỳ vọng cao nhất.

Một vấn đề với cách tiếp cận này là số chiến lược có thể cực kỳ lớn, hoặc thậm chí vô hạn. Một vấn đề khác là các giá trị trả về có thể ngẫu nhiên, khi đó sẽ cần đến một lượng lớn các mẫu để có thể ước lượng chính xác kết quả trả về của mỗi chiến lược. Cách tiếp cận trực tiếp là cơ sở cho các thuật toán dùng trong ngành Robotic tiến hóa.

Các vấn đề của cách tiếp cận trực tiếp có thể được làm giảm nhẹ nếu ta giả thiết một cấu trúc nào đó trong bài toán và bằng cách nào đó cho phép các mẫu thu được từ một chiến lược này có thể được ảnh hưởng tới các ước lượng cho một chiến lược khác. Cách tiếp cận hàm giá trị thực hiện điều này bằng cách chỉ giữ một tập các ước lượng về các giá trị trả về của một chiến lược π (thường là chiến lược hiện tại hoặc chiến lược tối ưu).Trong các cách tiếp cận như vậy, người ta cố gắng ước lượng một trong hai hàm: giá trị trả về nếu xuất phát từ trạng thái s và theo chiến lược π như sau,

V(s) = E[R|s,π],

hoặc giá trị trả về kỳ vọng khi thực hiện hành động a trong trạng thái s và theo chiến lược π nghĩa là,

Q(s,a) = E[R|s,π],

Nếu có sẵn chiến lược tối ưu Q, ta luôn có thể chọn các hành động tối ưu đơn giản bằng cách tại mỗi trạng thái chọn hành động với giá trị cao nhất. Để thực hiện được điều này với V, ta phải có một mô hình môi trường, dưới dạng các xác suất P(s'|s,a), cho phép tính Q bằng công thức

Q ( s , a ) = ∑ s ′ V ( s ′ ) P ( s ′ | s , a ) , {\displaystyle Q(s,a)=\sum _{s'}V(s')P(s'|s,a),}

hoặc ta có thể sử dụng các phương pháp Actor-Critic, trong đó mô hình được chia làm hai phần: phần critic giữ ước lượng giá trị trạng thái V, và phần actor có trách nhiệm chọn các hành động thích hợp với mỗi trạng thái.

Cho trước một chiến lược cố định π, việc ước lượng E[R|.] đối với γ=0 là đơn giản, do ta chỉ phải lấy trung bình của các khoản thưởng trực tiếp. Cách dễ thấy nhất để thực hiện việc này với γ>0 là lấy trung bình của tổng trả về sau mỗi trạng thái. Tuy nhiên, kiểu lấy mẫu Monte Carlo đòi hỏi MPD phải kết thúc.

Do đó, nói chung việc ước lượng γ > 0 {\displaystyle \gamma >0} không dễ. Thực ra, việc này lại khá đơn giản khi ta nhận ra rằng giá trị kỳ vọng của R tạo nên một phương trình Bellman đệ quy: E [ R | s t ] = r t + γ E [ R | s t + 1 ] {\displaystyle E[R|s_{t}]=r_{t}+\gamma E[R|s_{t+1}]}

Bằng cách thay thế các giá trị kỳ vọng trên bằng các ước lượng của ta, V, và thực hiện thuật toán gradient descent với hàm chi phí lỗi bình phương, ta thu được TD(0) - thuật toán học temporal difference learning. Trong trường hợp đơn giản nhất, tập hợp các trạng thái và hành động đều là rời rạc và ta giữ các ước lượng dạng bản cho mỗi trạng thái. Các phương pháp cặp đôi trạng thái-hành động là SARSA và Q-Learning. Tất cả các phương pháp đều có các mở rộng mà nhờ đó một kiến trúc xấp xỉ nào đó được sử dụng, mặc dù trong một số trường hợp, sự hội tụ không được đảm bảo sẽ xảy ra. Các ước lượng thường được cập nhật bởi một dạng gradient descent, tuy rằng gần đây đã có các phương pháp bình phương tối thiểu cho các trường hợp xấp xỉ tuyến tính.

Các phương pháp trên không những đều hội tụ về các ước lượng đúng cho một chiến lược cố định, và còn có thể được dùng để tìm chiến lược tối ưu. Việc này thường được thực hiện bằng cách theo một chiến lược π được rút ra từ các ước lượng hiện tại, nghĩa là bằng cách hầu như luôn luôn chọn hành động với lượng giá cao nhất, và thỉnh thoảng chọn các hành động ngẫu nhiên để khám phá không gian. Các chứng minh cho sự hội tụ tới chiến lược tối ưu cũng tồn tại đối với các thuật toán nói đến ở trênvới một số điều kiện nhất định. Tuy nhiên tất cả các chứng minh này chỉ chứng tỏ sự hội tụ tiệm cận, và về lý thuyết người ta còn biết rất ít về hành vi của các thuật toán học tăng cường trong trường hợp mẫu nhỏ, ngoại trừ trong các điều kiện tham số (setting) rất hạn chế.

Một phương pháp khác để tìm chiến lược tối ưu là tìm thẳng trong không gian các chiến lược. Phương pháp không gian chiến lược định nghĩa chiến lược là một hàm có tham số π(s,θ) với các tham số θ. Thông thường, một phương pháp leo đồi (gradient method) được áp dụng để điều chỉnh các tham số. Tuy nhiên, việc áp dụng các phương pháp leo đồi không đơn giản, do không có thông tin nào về độ dốc (gradient information) được giả thiết. Thay vào đó, chính độ dốc phải được ước lượng từ các mẫu nhiều nhiễu (noisy samples) của kết quả trả về. Do điều này làm tăng mạnh chi phí tính toán, nên việc sử dụng một phương pháp leo đồi mạnh hơn là leo đồi độ dốc cao nhất(steepest gradient descent) có thể có lợi hơn. Các phương pháp leo đồi dùng cho không gian chiến lược đã được sự quan tâm lớn trong 5 năm trở lại đây và giờ đã đạt đến giai đoạn tương đối chính muồi, nhưng lĩnh vực nghiên cứu này vẫn còn hoạt động. Có nhiều cách tiếp cận khác, chẳng hạn luyện thép (simulated annealing), có thể dùng để khám phá không gian chiến lược. Các nghiên cứu về các kỹ thuật này ít phát triển hơn.